A computer network generally includes a number of devices, including switches, routers and hubs, connected so as to allow communication among the devices. The devices within a network are often categorized into two classes: end stations such as workstations, desktop PCs, printers, servers, hosts, fax machines, and devices that primarily supply or consume information; and network devices such as gateways, switches and routers that primarily forward information between the other devices.
Network devices ordinarily operate on a continuous basis. Each device has one or more circuit boards, a microprocessor and a memory, and runs a control program. In general, networks often include several different types of data switching and routing devices. These network devices may have different physical characteristics. New devices, with characteristics that are presently unknown, are constantly being developed. In addition, the characteristics of many network devices may change over time. For example, characteristics of the network devices change when subsystems like boards, network interface modules, and other parts are added or removed from a device.
Many networks are managed, supervised and maintained by a network administrator or network manager. To properly maintain a network, the network administrator needs to have up-to-date information available about the devices in the network, how the devices are interconnected, and how data packets move among devices along logical and physical paths. The Open Systems Interconnection (“OSI”) network reference model is useful in classifying logical communication layers of network devices that can be used to collect network management information. Layer 2 and Layer 3 refer to the data link layer and the network layer respectively in the OSI model.
Layer 2 connectivity information may be used by the network administrator to determine and understand the physical topology of the network. The topology is a representation of the type of devices that are currently included in the network and how the interfaces of these devices are physically linked. Layer 3 information describes logical connectivity between a source and a destination device as specified by intermediary Layer 3 routing devices.
An effective network management system would create a topology based on both the logical connections of network devices, and the physical connection information. Not only would the network management system be capable of logically identifying to which network a particular device is linked, based on Layer 3 information, it would also indicate how individual devices are physically linked together, based on Layer 2 information. Thus, an administrator could determine the actual interface links or physical connectivity of each of the devices. This information may be critical in determining how the network can be expanded or upgraded, or in troubleshooting. Certain proprietary discovery protocols have been developed to help identify how the interfaces of each device are physically linked within a network, based on Layer 2 information. For example, the Cisco Discovery Protocol (“CDP”), which is used in products that are commercially available from Cisco Systems, Inc., San Jose, Calif., is a low-level communication protocol that can help a network management system identify how devices are linked in a network. When a device supporting CDP sends a message to another device, the message includes a packet that contains its IP address and an interface descriptor. The interface descriptor represents the logical name of the port from which the message was sent. The information is stored at the receiving device and may be used to determine how two devices are physically connected.
However, knowledge of the physical topology of the network may not be sufficient for diagnosing an error in the network. To diagnose certain errors, logical path information is needed. One technique of gathering information on errors and configuration in a network that uses Internet Protocol (“IP”) is path tracing for an IP packet. Path information defines the traversal of a packet or a sequence of packets from a source device to a destination device, whereas topology information defines either the physical or logical layout of a network without taking into account factors that affect the path traversed by a packet. The factors that affect the path traversed by a packet include spanning tree blocking, route determination, network misconfiguration, access-list prohibition, cable cuts, etc.
FIG. 1A is a block diagram of a network that illustrates the difference between path and topology. Access Switches 102a, 104a are connected to users 102b, 104b respectively. Core Switch 110 is connected to Backbone 112. Core Switch 110 is connected to A Switch 102a and Access Switch 104a by intermediary devices such as Distribution Switch 106 and Root Bridge 108.
Access Switch 102a is connected to Distribution Switch 106 by Connection 118 through Access Ports 118a, 118b. Similarly, Access Switch 102a is connected to Root Bridge 108 by Connection 114 and through Access Ports 114a, 114b. 
Access Switch 104a is connected to Distribution Switch 106 by Connection 116 through Access Ports 116a, 116b. Also, Access Switch 104a is connected to Root Bridge 108 by Connection 120 and through Access Ports 120a, 120b. Core Switch 110 is connected to Distribution Switch 106 by Connection 122 and Access Ports 122a, 122b. Core Switch 110 is also connected to Root Bridge 108 by Connection 124 and Access Ports 124a, 124b. 
The layout of the network as depicted by the connections between the devices in FIG. 1A is referred to as the topology of the network. In contrast, the path that a packet would traverse from a source device to a destination device would vary depending on the Spanning Tree information for the network.
The Spanning Tree protocol, defined in IEEE Specification 802.1D, is a method used to determine a “loop-free” subset of a network topology. In the context of Spanning Tree, a “loop” is a path on which packets never reach their destination, but cycle repeatedly through a series of devices that comprise the loop. FIG. 1B is a block diagram that illustrates a loop in a network. A packet that may be originating from Access Switch 102a and destined for Access Switch 104a would never reach Access Switch 104a by traversing the loop path comprising Connections 118, 122, 124, 114.
By applying the Spanning Tree algorithm to a given network topology, loop paths are prevented by determining which access ports in the topology should be placed in a “blocked state” in order to create a loop-free Spanning Tree for the given network. For example, referring to FIG. 1A, Access Ports 114a, 114b, 116a, 116b can be placed in a blocked state as a result of applying a Spanning Tree algorithm to the network of FIG. 1A. Because Access Ports 114a, 114b, 116a, 116b are in the blocked state, a loop-free Spanning Tree is achieved, comprising Connections 118, 122, 124, 120, and Connections 114, 116 are shown as dotted lines to indicate that they are not part of the Spanning Tree. Thus, for the purposes of illustration, the solid lines as shown in FIG. 1C indicate the Spanning Tree.
For most accurate path tracing, it is desirable for IP path tracing to be performed both at Layer 3 and Layer 2. A Layer 2 IP path is also referred to as a “data link path”. A data link path is important for network monitoring and diagnostics because the information obtained from IP path tracing performed at Layer 3 may be insufficient. For example, IP path tracing at Layer 3 identifies a path from router to router and does not identify the actual network devices such as LANs switches and bridges that an IP packet may traverse to get from a source device to a destination device. Thus, the path between any two Layer 3 devices may traverse entire networks of devices that operate at Layer 2.
Tools such as the UNIX-based traceroute computer program and the Windowsbased tracert computer program are used to perform IP path tracing at Layer 3. However, techniques for direct IP tracing at Layer 2 that are suitable for a wide range of technologies including Ethernet, Local Area Network Emulation, Token Ring, and EtherChannel are not available.
Based on the foregoing, there is a clear need for a method that can identify the data link path from a source device to a destination device on the network.
There is a specific need for a way to carry out IP Path tracing at OSI Layer 2 for use in network management functions.